// POJ3624 Charm Bracelet
// 陈锋
#include <algorithm>
#include <cmath>
#include <cstdio>

const int MAXN = 5000;
using namespace std;
int N, M, W[MAXN], D[MAXN], S[20 * MAXN];
int main() {
  scanf("%d %d", &N, &M);  // n为商品数量 m背包大小
  for (int i = 1; i <= N; i++) scanf("%d %d", &W[i], &D[i]);

  // 二维背包空间O(N*M)，对于本题而言为：3402*12880，所以空间太大
  // 采用滚动数组，空间降为O(M)
  // S(i,j):前i个珠子,总重不超过j所能获得的最大价值
  // S(i,j) = max(S(i-1,j), S(i-1,j-W(i)) + D[i])
  // 滚动数组，仅保留第2维度, S[j] = max(S[j],S[j-W[i]]+D[i]),
  // 按照从大到小的顺序更新数组
  for (int i = 1; i <= N; i++)
    for (int j = M; j >= W[i]; j--) S[j] = max(S[j], S[j - W[i]] + D[i]);
  printf("%d\n", S[M]);
  return 0;
}
// Accepted 282ms 432kB 659 G++ 2020-12-26 21:17:00 22233206